Abstract: Database encryption is an effective method to protect the sensitive data. However, encryption makes dataintegrity check on the data encrypted very difficult. An integrity check on character data in two steps is proposed based on a method of fast query over encrypted character data. In the first place, the coarse check is implemented and the encrypted value of the dataintegrity is computed to filter some unsatisfied data. Then, the exact check is implemented and the rest records are decrypted and checked. The whole dataintegrity check is finished after the two steps. The dataintegrity check in two steps is more secure and efficient without adding too much space.

Key words: encryped database, dataintegrity, checking in two steps